抢红包机器人 [思维题]
抢红包机器人 [思维题]
Wannafly Day5 G
题目来源：comet OJ
分析
由于题目要求至少存在一个机器人，所以我们必须先假设某一个人是机器人，然后以此向下推，推出所有必须是机器人的人，最后的总数就是机器人的最少数量。
那么，这个问题就变成了“第一个”机器人应该选谁的问题。事实上，由于不同人之间的关系是偏序的，即是可以传递的，譬如i比j快，j比k快，那么i为机器人时k也一定为机器人,所以我们可以直接用类似于floyd的方法推出对于任意的\(i,j\)，\(i\)是否比\(j\)快。然后我们只需要找到能够影响的\(j\)最少的\(i\)即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <iostream>
using namespace std;
int n,m,b,res,c[105],sum;
bool a[105][105];
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>b;
for(int j=1;j<=b;j++)
{
cin>>c[j];
for(int k=1;k<j;k++)
a[c[k]][c[j]]=1;
}
}
for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(a[i][k] == 1 && a[k][j] == 1)
a[i][j] = 1;
res=105;
for(int i=1;i<=n;i++){
sum=0;
for(int j=1;j<=n;j++)
sum+=a[j][i];
if(a[i][i]==0)
sum++;
res=min(sum,res);
}
cout<<max(1,res)<<endl;
return 0;
}
|